package stack.栈的应用;

import java.util.Stack;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * 1、定义一个栈stack，用来接收运算符；定义一个char类型数组chars，用于接收输出结果
 * 2、从左到右遍历字符串，遇到字符添加到输chars，遇到运算符栈为空入栈，不为空，
 * 当前运算符A和栈顶运算符B比较，如果A的优先级大于B，那么A入栈，否则A出栈，并添加到chars，B入栈
 * 3、遇到左括号入栈，右括号则进行出栈操作，直到匹配到左括号，出栈结束
 * 4、将栈中剩余元素加入到chars中
 * User:Mr.Du
 * Date:2021/6/19
 * Time:21:22
 */
public class 中缀转后缀 {

    public static void main(String[] args) {
        Stack<Character> stack = new Stack<>();
        String s = "(1+2)*3+4*5";
        System.out.println(s);
        String result = infixToPostFix(s, stack);
        System.out.println(result);
    }


    /**
     *
     * @param s        输入表达式
     * @param stack   存储操作符和括号
     * @return
     */
    public static String infixToPostFix(String s, Stack<Character> stack){
        int index = 0;
        char[] tmp = s.toCharArray();
        char[] chars = new char[s.length()];
        for(int i = 0;i < s.length();i++){
            //字符就进入输出数组
            if(tmp[i] >= '0' && tmp[i] <= '9'){
                chars[index++] = tmp[i];
            }else if(tmp[i] == '('){
                //左括号直接入栈
                stack.add(tmp[i]);
            }else if(tmp[i] == '+' || tmp[i] == '-'
                        || tmp[i] == '*'
                        || tmp[i] == '/'){
                //栈为空，直接入栈
                //不为空，如果当前栈顶元素是(,直接将当前字符入栈
                //如果栈顶元素的运算符小于当前运算符，则入栈
                //否则将栈顶元素赋值给输出chars，同时将当前字符入栈
                if(!stack.isEmpty()){
                    char c = stack.peek();
                    if(c == '('){
                        stack.push(tmp[i]);
                    } else if(getPriority(tmp[i],c)){
                        stack.push(tmp[i]);
                    }else{
                        chars[index++] = c;
                        stack.pop();
                        stack.push(tmp[i]);
                    }
                }else{
                    stack.push(tmp[i]);
                }

            }else if(tmp[i] == ')'){
                //如果是右括号，进行出栈操作，直到匹配到左括号为止，将出栈元素赋值给chars
                char c;
                while((c = stack.pop()) != '('){
                    chars[index++] = c;
                }

            }
        }
        //将栈中剩余元素赋值给chars
        while(!stack.isEmpty()){
            chars[index++] = stack.pop();
        }
        return String.valueOf(chars);
    }

    /**
     * 比较算术运算符大小
     * @param a
     * @param b
     * @return   true代表a的优先级高于b
     */
    public static boolean getPriority(char a,char b){
        if((a == '*' || a == '/') && (b == '+' || b == '-')) return true;
        return false;
    }
}
